import java.util.ArrayList;

/**
 * @version Create on 2012-11-2
 * @author Yinzi Chen
 */

public class GrayCode {

	boolean find;
	ArrayList<Integer> res;
	int n;
	boolean used[];

	public int bitcount(int k) {
		int cnt = 0;
		while (k > 0) {
			cnt += k % 2;
			k >>= 1;
		}
		return cnt;
	}

	public void search(int val, int depth) {
		if (depth + 1 == 1 << n) {
			if (bitcount(val) == 1) {
				find = true;
			}
			return;
		}
		if (find)
			return;
		used[val] = true;
		for (int i = 0; i < n; ++i) {
			int next = val ^ (1 << i);
			if (!used[next]) {
				used[next] = true;
				res.add(next);
				search(next, depth + 1);
				if (find)
					return;
				res.remove(res.size() - 1);
				used[next] = false;
			}
		}
	}

	public ArrayList<Integer> grayCode(int n) {
		this.n = n;
		find = false;
		res = new ArrayList<Integer>();
		used = new boolean[1 << n];
		res.add(0);
		search(0, 0);
		return res;
	}

	public static void main(String[] args) {
		GrayCode a = new GrayCode();
		ArrayList<Integer> res = a.grayCode(3);
		for (int i : res) {
			System.out.println(Integer.toBinaryString(i));
		}
	}

}
